[livres divers classés par sujet] [Informatique] [Algorithmique] [Programmation] [Mathématiques] [Hardware] [Robotique] [Langage] [Intelligence artificielle] [Réseaux]
[Bases de données] [Télécommunications] [Chimie] [Médecine] [Astronomie] [Astrophysique] [Films scientifiques] [Histoire] [Géographie] [Littérature]

Fixpoint logics on hierarchical structures

contributor FMI, Theoretische Informatik
creator Göller, Stefan
Lohrey, Markus
date 2005-06-24
description 38 pages
Hierarchical graph definitions allow a modular description of graphs using modules for the specification of repeated substructures. Beside this modularity, hierarchical graph definitions also allow to specify graphs of exponential size using polynomial size descriptions. In many cases, this succinctness increases the computational complexity of decision problems. In this paper, the model-checking problem for the modal $\mu$-calculus and (monadic) least fixpoint logic on hierarchically defined input graphs is investigated. In order to analyze the modal $\mu$-calculus, parity games on hierarchically defined input graphs are investigated. In most cases precise upper and lower complexity bounds are derived. A restriction on hierarchical graph definitions that leads to more efficient model-checking algorithms is presented.
format application/pdf
321585 Bytes
identifier  http://www.informatik.uni-stuttgart.de/cgi-bin/NCSTRL/NCSTRL_view.pl?id=TR-2005-04&engl=1
language eng
publisher Stuttgart, Germany, Universität Stuttgart
relation Technical Report No. 2005/04
source ftp://ftp.informatik.uni-stuttgart.de/pub/library/ncstrl.ustuttgart_fi/TR-2005-04/TR-2005-04.pdf
subject Complexity Measures and Classes (CR F.1.3)
Mathematical Logic (CR F.4.1)
parity games
mu-calculus
hierarchical structures
lfp
mlfp
model checking
title Fixpoint logics on hierarchical structures
type Text
Technical Report